/*
 * @lc app=leetcode id=41 lang=cpp
 *
 * [41] First Missing Positive
 */
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int len = nums.size();
        if (len < 1) {
            return 1;
        }

        for (int k=1; k<=len; k++) {
            while (nums[k-1] > 0 && nums[k-1] <= len && nums[k-1] != k) {
                if (nums[k-1] != nums[nums[k-1]-1])
                    std::swap(nums[k-1], nums[nums[k-1]-1]);
                else 
                    break;
            }
        }

        for (int i=0; i<len; i++) {
            if (nums[i] != i+1) {
                return i+1;
            }
        }
        return len+1;
    }
};

